package com.alu.sort;

import java.util.Arrays;

/**
 * 插入排序
 * 
 * @author Administrator
 *
 */
public class InsertSort extends AbstractSort {
	@Override
	public void sort(Comparable[] a) {
		for(int i=0; i<a.length; i++) {
			
			// 指向已经排好的序列中比当前值大的最小的值，默认指向第一个，意思是所有的值都比当前值大
			int bigger = 0;
			
			// 找到已排好序的序列中，第一个比当前值小的值，那么bigger就应该指向这个值之后
			for(int j=i-1; j>=0 ; j--) {
				if(this.less(a[j], a[i])) {
					bigger = j+1;
					break;
				}
			}
			
			// 从bigger开始到当前值位置的数组全部向右移动一位
			Comparable current = a[i];
			for(int x=i; x>bigger; x--) {
				a[x] = a[x-1];
			}
			
			// 将当前值放到bigger的位置
			a[bigger] = current;
		}
	}
}
